/*
 * @Author: _LJP 2634716776@qq.com
 * @Date: 2023-12-18 08:45:54
 * @LastEditors: _LJP 2634716776@qq.com
 * @LastEditTime: 2023-12-18 20:42:14
 * @FilePath: /my_-linux/Pro23/BinarySearchT1130/ReveiwBST/BinarySearchT.hpp
 * @Description: 这是默认设置,请设置`customMade`, 打开koroFileHeader查看配置 进行设置: https://github.com/OBKoro1/koro1FileHeader/wiki/%E9%85%8D%E7%BD%AE
 */
#pragma once

#include<iostream>

template<class K>
struct BSTNode
{
    BSTNode(const K&key = new K())
    :_left(nullptr),
    _right(nullptr),
    _key(key)
    {}
    BSTNode<K>* _left;
    BSTNode<K>* _right;
    K _key;
};

template<class K>
class BinarySearchTree
{
    typedef BSTNode<K> Node;

    public:

        /*
         *默认成员函数
         */

        //构造函数
        BinarySearchTree() = default;

        //拷贝构造函数
        BinarySearchTree(const BinarySearchTree<K> &node)
        {
            _root = _Copy(node._root);
        }

        //赋值运算符重载
        BinarySearchTree<K>& operator=(BinarySearchTree<K> node)
        {
            std::swap(_root,node._root);
            return *this;
        }
////////////////////////////////////////

        bool InsertR(const K& key)
        {
            return _InsertR(_root,key);
        }

        bool Insert(const K& key)
        {
            if(_root == nullptr){
                _root = new Node(key);
                return true;
            }
            Node* cur = _root;
            Node* parent ;

            while(cur)
            {
                parent = _root;
                if(key > cur -> _key)
                {
                    parent = cur;
                    cur = cur->_right;
                }
                else if(key < cur -> _key)
                {
                    parent = cur;
                    cur = cur->_left;
                }
                else return false;
            }
            //插入
            Node* newnode = new Node(key);
            
            if(key > parent->_key) parent->_right = newnode;

            else parent->_left = newnode;
            
            return true;
        }

        bool FindR(const K& key)
        {
            return _FindR(_root,key);
        }

        bool Find(const K& key)
        {
            Node* cur = _root;
            while (cur)
            {
                if(key > cur->_key) cur = cur->_right;
                else if (key < cur->_key) cur = cur->_left;
                else return true;
            }
            return false;
        }

        void InOrder()
        {
            _InOrder(_root);
            std::cout<<std::endl;
        }

        bool EraseR(const K& key)
        {
            return _EraseR(_root,key);
        }

        bool Erase(const K& key)
        {
            if(nullptr == _root) return false;
            Node* cur = _root;
            Node* parent = _root;
            while(cur){
                if(key > cur->_key)
                {
                    parent = cur;
                    cur = cur->_right;
                }
                else if(key < cur->_key)
                {
                    parent = cur;
                    cur = cur->_left;
                }
                else{
                    //删除
                    /*左或右为空*/
                    if (cur->_left == nullptr) // 左为空
                    {
                        if(cur == _root)
                        {
                            _root = _root->_right;
                            delete cur;
                            return true;
                        }

                        if(cur == parent->_left)
                            parent->_left = cur->_right;

                        else parent ->_right = cur->_right;
                        delete cur;
                        return true;
                    }

                    else if (cur->_right == nullptr) // 右为空
                    {
                        if (cur == _root)
                        {
                            _root = _root->_left;
                            delete cur;
                            return true;
                        }

                        if (cur == parent->_left)
                            parent->_left = cur->_left;

                        else
                            parent->_right = cur->_left;
                            delete cur;
                            return true;
                    }

                    /*
                     * 左右都不为空
                     * 取左子树的最大值或者右子树的最小值
                     */
                    else
                    {
                        //左子树的最大节点
                        Node* bigleft = cur->_left;
                        Node* p_bigleft = cur;
                        while(bigleft->_right)
                        {
                            p_bigleft = bigleft;
                            bigleft = bigleft->_right;
                        }
                        //找到并进行伪删除法
                        cur->_key = bigleft->_key;
                        if(p_bigleft->_left == bigleft)
                        {
                            p_bigleft->_left = bigleft->_left;
                        }
                        else
                        {
                            p_bigleft->_right = bigleft->_right;
                        }
                        delete bigleft;
                        return true;
                    }
                }
            }
            return false;
        }


        
    protected:
        bool _FindR(const Node *node ,const K& key)
        {
            if(key == node->_key) return true;
            if(key > node->_key) return _FindR(node->_right,key);
            else if(key < node->_key) return _FindR(node->_left,key);
            else return false;
        }

        bool _InsertR(Node*& node,const K& key)
        {
            if (node == nullptr)
            {
                node = new Node(key);
                return true;
            }

            if (key > node->_key)
                return _InsertR(node->_right, key);

            else if (key < node->_key)
                return _InsertR(node->_left, key);
                
            else return true;
        }

        bool _EraseR(Node*& node,const K&key)
        {
            if(key > node->_key)
                return _EraseR(node->_right , key);
            if(key < node->_key)
                return _EraseR(node->_left, key);

            else
            {   //单边为空
                if(node->_left == nullptr)
                {
                    Node* tmp = node;
                    node = node->_right;
                    delete tmp;
                    return true;
                }
                else if(node->_right == nullptr)
                {
                    Node *tmp = node;
                    node = node->_left;
                    delete tmp;
                    return true;
                }
                //左右都不为空
                else
                {
                    Node* bigleft = node->_left;
                    while(bigleft->_right)
                    {
                        bigleft = bigleft->_right;
                    }
                    node->_key = bigleft->_key;
                    _EraseR(node->_left,bigleft->_key);
                    return true;
                }
                return false;
            }
        }


        void _InOrder(Node* root)
        {
            if(root == nullptr) return ;

            _InOrder(root -> _left);

            std::cout << root -> _key <<" ";
            
            _InOrder(root -> _right);
        }

        Node* _Copy(const Node* node)
        {
            if(node == nullptr) return nullptr;
            Node* newnode = new Node(node->_key);
            newnode->_left = _Copy(node->_left);
            newnode->_right = _Copy(node->_right);
            return newnode;
        }
    private:
        Node* _root = nullptr;
};



